package algorithm.swordoff;

/**
 * 圆圈中最后剩下的数字
 *
 * 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
 *
 * 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
 *
 *
 * 反着推 总结一下反推的过程，就是 留下的元素对应当前index = (下一轮留下的index + m) % 本轮剩余数字的个数
 *
 *                       留下的元素对应当前index
 * 0 1 2 3 4 -> pop(2)     (0+3)%5 = 3
 * 3 4 0 1   -> pop(0)     (1+3)%4 = 0
 * 1 3 4     -> pop(4)     (1+3)%3 = 1
 * 1 3 1     -> pop(1)     (0+3)%2 = 1
 * 3                            0
 *
 * 或者动态规划,设所求为 f(n, m), 索引为0,1,2,3,...,n-1
 * 则 f(n, m) 踢掉的数字为 (m-1)%n 得到 f(n-1, m), 新索引0号元素为上一轮的 m%n = t, 则新索引为 t+0, t+1, ..., n, 0, ..., t-2
 * 不妨设 f(n-1, m) = t+x, 对应 f(n, m) 中的索引为 (t+x)%n, i.e. f(n, m) = (f(n-1, m) + t)%n
 * 初始状态 f(1, m) = 0
 *
 */

public class SQ62 {

    public int lastRemaining(int n, int m) {
        // 最后一轮剩下的必定是索引为0的元素
        int ans = 0;

        // 一共n个剩最后一个,说明总共执行n-1轮
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }

    public static void main(String[] args) {
        SQ62 sq62 = new SQ62();
        System.out.println(sq62.lastRemaining(11, 3));
    }

}
